#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    int minimumDeleteSum(string s1, string s2)
    {
        vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, -1));
        return memoryCache(s1, s2, 0, 0, dp);
    }

    int memoryCache(string &s1, string &s2, int i, int j, vector<vector<int>> &dp)
    {
        if (dp[i][j] != -1)
            return dp[i][j];
        if (i < s1.size() && j < s2.size())
        {
            int v1 = memoryCache(s1, s2, i + 1, j, dp) + (i > s1.size() ? 0 : s1[i]);
            int v2 = memoryCache(s1, s2, i, j + 1, dp) + (j > s2.size() ? 0 : s2[j]);
            dp[i][j] = min(v1, v2);
            if (s1[i] == s2[j])
            {
                dp[i][j] = min(dp[i][j], memoryCache(s1, s2, i + 1, j + 1, dp));
            }
        }
        else if (i < s1.size())
        {
            dp[i][j] = memoryCache(s1, s2, i + 1, j, dp) + (i > s1.size() ? 0 : s1[i]);
        }
        else if (j < s2.size())
        {
            dp[i][j] = memoryCache(s1, s2, i, j + 1, dp) + (j > s2.size() ? 0 : s2[j]);
        }
        else
        {
            dp[i][j] = 0;
        }
        return dp[i][j];
    }
};
int main()
{
    cout << "Code712" << endl;
    Solution s;
    //string s1 = "delete", s2 = "leet";
    string s1 = "s", s2 = "";
    cout << s.minimumDeleteSum(s1, s2) << endl;
    return 0;
}